// 给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。

// 举个例子，A = "abcd"，B = "cdabcdab"。

// 答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

// 注意:

//  A 与 B 字符串的长度在1和10000区间范围内。

#include <string>

using namespace std;

class Solution1 {
public:
    int repeatedStringMatch(string A, string B) {
        int n1 = A.size();
        int n2 = B.size();
        int count{1}; // s中字符串A的个数
        string s{A};
        while (s.size() < n2) {
            s += A;
            ++count;
        }
        if (s.find(B) != string::npos) return count;
        s += A; // 如果不是子串，就在加一个A
        return (s.find(B) != string::npos) ? count + 1 : -1; // 如果还不是子串，就返回-1
    }
};

// 算出最多需要的A字符串个数，就是B.size()/A.size() + 2
class Solution2 {
public:
    int repeatedStringMatch(string A, string B) {
        int n1 = A.size();
        int n2 = B.size();
        string s{A};
        for (int i{1}; i <= n2/n1+2; ++i) {
            if (s.find(B) != string::npos) return i;
            s += A;
        }
        return -1;
    }
};

// 不用find函数，逐个字符比较
class Solution3 {
public:
    int repeatedStringMatch(string A, string B) {
        int n1 = A.size();
        int n2 = B.size();
        for (int i{0}; i < n1; ++i) {
            int j{0};
            while (j < n2 && A[(i+j) % n1] == B[j]) ++j;
            if (j == n2) return (i+j-1)/n1+1;
        }
        return -1;
    }
};

#include "../stdc++.h"

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        // 先判断字母种类。种类都不够，显然不行。
        unordered_set<char> us_a(a.begin(), a.end());
        unordered_set<char> us_b(b.begin(), b.end());
        if (us_a.size() < us_b.size()) {
            return -1;
        }
        int m = a.size();
        int n = b.size();
        int res = n / m;
        string cur{""};
        for (int i{0}; i < res; ++i) {
            cur += a;
        }
        for (int i{0}; i < 3; ++i) {
            if (cur.find(b) != std::string::npos) {
                return res;
            } else {
                ++res;
                cur += a;
            }
        }
        return -1;
    }
};

// KMP
class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        // 先判断字母种类。种类都不够，显然不行。
        unordered_set<char> us_a(a.begin(), a.end());
        unordered_set<char> us_b(b.begin(), b.end());
        if (us_a.size() < us_b.size()) {
            return -1;
        }
        int m = a.size();
        int n = b.size();
        int res = n / m;
        string cur{""};
        for (int i{0}; i < res; ++i) {
            cur += a;
        }
        for (int i{0}; i < 3; ++i) {
            if (KMP(cur, b)) {
                return res;
            } else {
                ++res;
                cur += a;
            }
        }
        return -1;
    }
private:
    bool KMP(const string& s, const string& t) {
        int len_s = s.size();
        int len_t = t.size();
        vector<int> next = get_next(t);
        int i{0};
        int j{0};
        while ((i < len_s) && (j < len_t)) {
            if ((j == -1) || (s[i] == t[j])) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        return j == len_t;
    }
    // next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置。
    // 因为下标从0开始的，k值实际是j位前的子串的最大重复子串的长度。
    vector<int> get_next(const string& t) {
        int n = t.size();
        vector<int> next(n + 1, 0);
        next[0] = -1;
        int i{-1};
        int j{0};
        while (j < n) {
            if ((i == -1) || (t[i] == t[j])) {
                ++i;
                ++j;
                next[j] = i;
            } else {
                i = next[i];
            }
        }
        return next;
    }
};
